package Solution.problem063;

/**
 * @program Leetcode
 * @description:
 * @author: lishangsheng
 * @create: 2019/06/06 10:21
 */
public class Solution {
    private static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid==null||obstacleGrid.length==0){
            return 0;
        }
        int n=obstacleGrid.length;
        int m=obstacleGrid[0].length;
        //m列n行
        if (m == 0) {
            return 0;
        }
        if(obstacleGrid[0][0]==0){
            obstacleGrid[0][0]=1;
        }else {
            obstacleGrid[0][0]=-1;
        }
        //上边和左边都是只有一次
        for (int i = 1; i < m; i++) {
            if(obstacleGrid[0][i]!=0||obstacleGrid[0][i-1]<0){
                obstacleGrid[0][i]=-1;
            }else{
                obstacleGrid[0][i] = 1;
            }
        }
        for (int j = 1; j < n; j++) {
            if(obstacleGrid[j][0]!=0||obstacleGrid[j-1][0]<0){
                obstacleGrid[j][0] = -1;
            }else {
                obstacleGrid[j][0] = 1;
            }
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                /*左边一个格子的路径数量+上面一个格子的路径数量*/
                if(obstacleGrid[i][j]!=0){
                    obstacleGrid[i][j]=-1;
                    continue;
                }
                int left;
                if(obstacleGrid[i][j - 1]==-1){
                    left=0;
                }else{
                    left=obstacleGrid[i][j - 1];
                }
                int top;
                if(obstacleGrid[i - 1][j]==-1){
                    top=0;
                }else{
                    top=obstacleGrid[i - 1][j];
                }
                obstacleGrid[i][j] = left+ top;
            }
        }

       // System.out.println(JSON.toJSONString(obstacleGrid));
        return obstacleGrid[n - 1][m - 1]>0?obstacleGrid[n - 1][m - 1]:0;
    }

    public static void main(String[] args) {
        int[][] array = new int[][]{
                {0, 0, 0},
                {0, 1, 0},
                {0, 0, 0}
        };
        System.out.println(uniquePathsWithObstacles(array));

        int[][] array2 = new int[][]{
                {1},
        };
        System.out.println(uniquePathsWithObstacles(array2));

        int[][] array3 = new int[][]{
                {0},
        };
        System.out.println(uniquePathsWithObstacles(array3));

        int[][] array4 = new int[][]{
                {1,0},
        };
        System.out.println(uniquePathsWithObstacles(array4));
    }
}
